1. Field of the Invention
The present invention relates to a data encryption system implemented on a computer having a cache memory placed between a processor and a main memory, and in particular to data encryption system and method of encrypting data using transformation tables such as substitution tables.
2. Description of the Related Art
Symmetric block ciphers such as DES (Data Encryption Standard) ciphers and FEAL (Fast data Encipherment ALgorithm) ciphers typically employ successive iterations, each of which contains operations of exclusive-OR, substitution and coordinate permutation. The substitution is performed by using so-called S boxes, which are substitution boxes or, simply, look-up tables having a predetermined number of possible inputs. In general, S boxes are classified according to the number of input bits, each S box being indicated by Si box, wherein i is the number of input bits, such as S7 box and S9 box. During cipher or decipher for one block, each Si box is referred to a plurality of times.
An example of a conventional encryption system will be described with reference to FIGS. 1A, 1B and 2. As shown in FIG. 1A, an encryption system is composed of a program-controlled processor (here, CPU) 1, a memory (main memory) 2 into which an encryption program 3 is loaded from a disk or the like, and a cache memory 4. The cache memory 4 is connected to the CPU 1 by a processor bus 5 composed of data lines, address lines and control lines and is connected to the memory 2 by a memory bus 6 composed of data lines, address lines and control lines.
As known well, the cache memory 4 is a small-capacity memory allowing high-speed access compared with the main memory 2. The cache memory 4 stores the contents of frequently accessed main memory locations and addresses. When the CPU 1 issues a request for data or instruction through the processor bus 5, the cache memory 4 checks to see whether it holds the same. If it holds the same (cache hit), then the cache memory 4 returns the data to the CPU 1. If it does not hold the same (a cache miss), the cache memory 4 reads a predetermined size of data including the requested data or instruction from the main memory 2 through the memory bus 6 and stores the predetermined size of data while transferring the requested data or instruction to the CPU 1. The predetermined size of data read from the main memory 2 is, for example, 32 bytes or 128 bytes. Since instructions located near the previously executed address are frequently executed, the cache hit rate can be increased by storing such a larger size of data in advance into the cache memory 4, resulting in high-speed access.
The encryption program 3 instructs the CPU 1 to perform a symmetric block cipher such as DES or FEAL cipher. Its program architecture is shown in FIG. 1B. A substitution table section 305 composed of a predetermined number of substitution tables is previously provided in the encryption program 3. For example, each substitution table of the substitution table section 305 has 16 entries each having addresses 0-F(H) assigned thereto and having hexadecimal numbers 0-F stored therein, as shown in FIG. 2. For example, in the case of input bits “10000”=0 (H), 8 (H) stored at the address 0 (H) is read out and a corresponding binary number “1000” is output. As described before, the substitution table section 305 is referenced a plurality of times to perform substitution by a data transformation section 304.
There are proposed several cryptanalytic methods of analyzing the key used in an encryption algorithm, for example, Exhaustive key search, Differential cryptanalysis, and Linear cryptanalysis.
Recently, new cryptanalysis called timing attack which mainly targets public-key encryption systems has been proposed by Paul C. Kocher (“Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems” Advances in Cryptology: Proceedings of Crypto 96, Plenum Press, 1995, pp 104-113). According to timing attacks, the secret key candidates of a cryptosystem can be narrowed based on differences in the amount of time required to perform power-residue operation that is basic to the public-key cipher.
A technique for preventing time attacks has been disclosed in Japanese Patent Application Unexamined Publication No. 10-222065. A basic idea of this countermeasure is to change in delay time of critical path for each power-residue operation.
However, in the case where the above-described encryption system using the substitution table is implemented on a computer having the cache memory 4 therein, a cache-attack cryptanalysis method, which was found by the present inventor and will be described later, can narrow the key candidates of the encryption system to finally find the entire key by measuring the amount of time required to encrypt data. Since the cache-attack cryptanalysis method can be applied to symmetric ciphers which do not use any power-residue operations, the countermeasure described in the Japanese Patent Application Unexamined Publication No. 10-222065 becomes ineffective.
Cache-Attack Cryptanalysis
As shown in FIG. 3, it is assumed that an encryption device calculates an exclusive OR (XOR) of plain text P0 and an n-bit key k0 to reference an substitution table S and an exclusive OR of plain text P10 and ann-bit key k1 to reference the substitution tables. When different entries are looked up in the substitution table S, the following relationships are obtained:P0.XOR.k0≠P1.XOR.k1, andP0.XOR.P1≠k0.XOR.k1=Δk  (1),where Δk is hereinafter called a key differential.
The formula (1) can be generalized from 2-table model to n-table model as follows:Pi.XOR.ki≠Pj.XOR.kj, andPi.XOR.Pj≠ki.XOR.kj=Δkij  (2),where i, j=1, 2, 3, . . . n.
The formula (2) indicates the case where the substitution table S is references n times during cipher/decipher process. In this case, with regard to any two plain text Pi and Pj, an exclusive OR of Pi and an n-bit key ki and an exclusive OR of Pj and an n-bit key kj look up different entries in the same substitution table S and further an exclusive OR of Pi and Pj is not equal to a key differential Δkij which is an exclusive OR of any two keys ki and kj. When such a key differential Δ kij is obtained, the range of exhaustive key search can be narrowed to 22N−2N. For example, when N bits of Δk=k0.XOR.k1 are obtained, the exhaustive search for N bits of k0 causes N bits of the other k1 to be calculated from the relationship: k1=k0.XOR.Δk. Accordingly, the exhaustive search for 2N bits of k0 and k1 can be reduced to that for only N bits of k0.
How to obtain the key differential Δkij will be described with reference to FIGS. 4A and 4B. First, as shown in FIG. 4A, a counter table is prepared, which contains initialized counters each corresponding to all possible values of the key differential Δkij.
Subsequently, an arbitrary pair of plain texts is extracted from a set of plain texts, which would cause different entries to be looked up in the substitution table in all rounds of the cipher process. Thereafter, a counting step of incrementing by one a counter corresponding to a value of the key differential Δkij which is equal to an exclusive OR of the extracted pair of plain texts is repeatedly performed for all pairs of the plain texts. As a result, the counters of the counter table are updated as shown in FIG. 4B. The counters of the counter table each having finally obtained counter values are searched for a counter value of zero or an extreme small value to identify a corresponding counter, which determines a key differential Δkij. It should be noted that the extreme small value is a value depending on the provability of satisfying the formula (2).
There will be described a method of obtaining a set of arbitrary plain texts which will cause different entries to be looked up in the substitution table S in all or a considerable amount of accesses in the case where the substitution table S is referenced n times in a cipher/decipher process.
However, when applying such an encryption program on the conventional encryption system having the cache memory 4 as shown in FIG. 1A, there are developed differences in the amount of time required to perform encryption/decryption depending on given plain/cipher text. Provided with different plain texts, the data transformation section 304 may lookup different entries in the substitution table, resulting in different cache hit rates when the substitution table is accessed. In other words, among given plain/cipher texts, one providing the highest rate of cache miss needs the longest encryption time. It is estimated that a plain/cipher text providing the highest rate of cache miss increases the possibility of causing different entries to be looked up in the substitution table in all or a considerable amount of accesses.
Verification
The present inventor verified the above estimation using a well-known cipher algorithm MISTY1 proposed by Mitsuru Matsui. Detailed descriptions of MISTY1 are provided by Mitsubishi Electric Corporation (see “Block Cipher algorithms MISTY1 and MISTY2” version 1.11 Oct. 2, 1996, and “Sample Programs of MISTY1 in C Language” version 1.00 Jul. 22, 1996).
Referring to FIGS. 5A-5D, MISTY1 is secret-key cipher with 64-bit data block and 128-bit secret key, including a data randomizing section, which uses two functions FOi and FLi. The function FOi uses function FIij, which uses two substitution tables S7 and S9. The substitution table S9 has a 9-bit input and 512 entries (each 32-bit entry in Sample-Program version). The substitution table S7 has a 7-bit input and 128 entries (each 8-bit entry in Sample-Program version).
The data randomizing section includes 8 functions FO1-FO8, each (FOi) of which includes 3 functions FIi1-FIi3. Each of the 3 functions FIi1-FIi3 references the substitution table S9 twice and the substitution table S7 once. Accordingly, during an encryption process, the substitution table S9 is used 48 times (=8×3×2) and the substitution table S7 is used 24 times (=8×3×1).
FIG. 6 shows the distribution of the number of plain texts with respect to cipher time when a number of plain texts are encrypted by MISTY1. FIG. 7 shows the relationship between cipher time and the number of operation entries in substitution table S9. FIG. 8 shows the relationship between cipher time and the number of operation entries in substitution table S7. The number of operation entries is defined as the number of entries, which are used for encryption in a substitution table. The maximum number of operation entries is 48 in the substitution table S9 and 24 in the substitution table S7.
It is understood from FIGS. 6 and 7 that a plain text taking T or more cipher time causes different entries to be looked up in the substitution table S9 for almost all accesses. Therefore, cache miss occurs every time, thereby taking much time for encryption. On the other hand, as shown in FIG. 8, in the substitution table S7, the distribution in the number of operation entries is approximately kept constant independently of the cipher time. Since the substitution table S7 is a small table with 128 entries, almost all entries are loaded into the cache memory 4 after miss hit has been repeated several times, thereby the occurrence of miss hit disappearing. In contrast, the substitution table S9 is a large table with 512 entries and therefore the occurrence of miss hit will not disappear. Such an operation-entry distribution difference between the substitution tables S7 and S9 makes the above-described cache attacks ineffective on the substitution table S7 and effective on the substitution table S9.
FIG. 9 shows an operation of extracting a set of plain texts having a high probability that the substitution table S9 is accessed about 48 times during cipher process. First, the cipher program of MISTY1 is loaded on the memory of a computer (step 101). Thereafter, a plain text is generated using random numbers (step 102) and the cache memory of the computer is cleared (step 103). The generated plain text is set as a plain text to be encrypted (step 104) and the plain text to be encrypted is encrypted by MISTY1 encryption and the time required for encryption is measured (step 105). Subsequently, it is determined whether the measured encryption time is equal to or greater than a predetermined threshold T (step 106). The threshold T is determined so that a necessary and sufficient number of plain texts can be obtained so as to stand the formula (2). The higher the probability of standing the formula (2), the lower the necessary number of plain texts. When the measured encryption time is equal to or greater than the predetermined threshold T (YES in step 106), the plain text is stored (step 107) and the control goes back to the step 102. When the measured encryption time is not greater than the predetermined threshold T (NO in step 106), the control goes back to the step 102 without storing the plain text. The steps 102-107 are repeatedly performed to obtain a sufficient number of plain texts having a high probability that the substitution table S9 is accessed about 48 times during cipher process.
Based on the plain texts obtained like this, the key differential Δk is determined using the method as shown in FIGS. 4A and 4B and the key candidates of the encryption system are narrowed. And finally the entire key is determined by using exhaustive search of the narrowed key candidates to determine the remaining bit values of the key.
As described above, in an encryption system implementing the encryption program using substitution tables on a computer having a cache memory, the cache-attack cryptanalysis method can narrow the key candidates of the encryption system to finally find the entire key by measuring the amount of time required to encrypt data. Accordingly, the cache-attack cryptanalysis method may be a kind of timing attack. Since the cache-attack cryptanalysis method can be applied to symmetric ciphers which do not use any power-residue operations, the countermeasure described in the Japanese Patent Application Unexamined Publication No. 10-222065 becomes ineffective.